/**
 * Copyright (c) 2004-2006 Regents of the University of California.
 * See "license-prefuse.txt" for licensing terms.
 */
package prefuse.data.util;

import java.util.ArrayList;
import java.util.Iterator;

import prefuse.data.Node;

/**
 * A depth-first iterator over the subtree rooted at given node.
 * 
 * @author <a href="http://jheer.org">jeffrey heer</a>
 */
public class TreeNodeIterator implements Iterator {

    private ArrayList m_stack;
    private Node m_root;
    private boolean m_preorder = true;

    /**
     * Create a new TreeNodeIterator over the given subtree.
     * @param root the root of the subtree to traverse
     */
    public TreeNodeIterator(Node root) {
        this(root, true);
    }

    /**
     * Create a new TreeNodeIterator over the given subtree.
     * @param root the root of the subtree to traverse
     * @param preorder true to use a pre-order traversal, false
     *  for a post-order traversal
     */
    public TreeNodeIterator(Node root, boolean preorder) {
        m_preorder = preorder;
        m_root = root;
        m_stack = new ArrayList();
        m_stack.add(root);

        if (!preorder) {
            for (Node n = root.getChild(0); n != null; n = n.getChild(0))
                m_stack.add(n);
        }

    }

    /**
     * @see java.util.Iterator#hasNext()
     */
    public boolean hasNext() {
        return !m_stack.isEmpty();
    }

    /**
     * @see java.util.Iterator#next()
     */
    public Object next() {
        Node c, x = null;
        if (m_preorder) {
            x = (Node) m_stack.get(m_stack.size() - 1);
            if ((c = x.getChild(0)) != null) {
                m_stack.add(c);
            } else if ((c = x.getNextSibling()) != null) {
                m_stack.set(m_stack.size() - 1, c);
            } else {
                m_stack.remove(m_stack.size() - 1);
                while (!m_stack.isEmpty()) {
                    c = (Node) m_stack.remove(m_stack.size() - 1);
                    if (c == m_root) {
                        break;
                    } else if ((c = c.getNextSibling()) != null) {
                        m_stack.add(c);
                        break;
                    }
                }
            }
        } else {
            x = (Node) m_stack.remove(m_stack.size() - 1);
            if (x != m_root && (c = x.getNextSibling()) != null) {
                for (; c != null; c = c.getChild(0)) {
                    m_stack.add(c);
                }
            }
        }
        return x;
    }

    /**
     * Throws an UnsupportedOperationException
     * @see java.util.Iterator#remove()
     */
    public void remove() {
        throw new UnsupportedOperationException("Remove not supported");
    }

} // end of class TreeNodeIterator
